package code.lru;


import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LRUCache2 {
    private int capacity;
    private Map<Integer, Integer> cache;
    private LinkedList<Integer> keyList;

    public LRUCache2(int _capacity) {
        capacity = _capacity;
        cache = new HashMap<>();
        keyList = new LinkedList<>();
    }

    public void put(Integer key, Integer value) {
        if (!cache.containsKey(key)) {
            if (cache.size() >= capacity) {
                // 移除链表头部元素
                int pollKey = keyList.removeLast();
                cache.remove(pollKey);
            }
            cache.put(key, value);
            // 将key放到链表头部
            keyList.addFirst(key);
            return;
        }
        cache.put(key, value);
        // 将key放到链表末尾
        keyList.remove(key);
        keyList.addFirst(key);
    }

    public int get(Integer key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        int value = cache.get(key);
        // 将key放到链表末尾
        keyList.remove(key);
        keyList.addFirst(key);
        return value;
    }

    public String Print() {
        return Arrays.toString(keyList.toArray());
    }

    public static void main(String[] args) {
        LRUCache2 lru = new LRUCache2(5);
        lru.put(1,1);
        lru.put(2,2);
        lru.put(3,3);
        lru.put(4,4);
        lru.put(5,5);
        System.out.println(lru.Print()); // 5,4,3,2,1
        lru.put(6,6);
        System.out.println(lru.Print()); // 6,5,4,3,2
        int value = lru.get(2);
        System.out.println(value); // 2
        System.out.println(lru.Print()); // 2,6,5,4,3
        lru.put(6,5);
        System.out.println(lru.Print()); // 6,2,5,4,3
    }
}
